/*
 * Eine Instanz von SortedSet stellt eine als einfache
 * Liste implementierte Menge dar, deren Elemente aufsteigend
 *  sortiert sind. Ein Typparameter bestimmt den Typ der Elemente. 
 *  Die Elemente muessen eine Methode faster mit einem Parameter unterstuetzen, 
 *  die genau dann true zurueckgibt, wenn this (auf nicht naeher bestimmte Weise) 
 *  schneller als das uebergebene Argument ist. 
 *  SortedSet implementiert folgende Methoden:
 *  
 *  -insert nimmt ein Argument, das an geeigneter Stelle eingefuegt wird,
 *   wenn nicht bereits ein identisches Element vorhanden war.
 *    Mehrere gleiche aber nicht identische Elemente duerfen in der Menge sein.
 *    
 *  - iterator liefert als Ergebnis einen Iterator (mit den Methoden next und hasNext),
 *  ueber den nacheinander auf alle Elemente der Menge in aufsteigender Reihenfolge
 *  zugegriffen werden kann.
 */
public class AnnotatedSet<Typ extends fasterInterface<Typ>,Typ2 extends fasterInterface<Typ2>> implements An_List_interface<Typ,Typ2>
{
	//Leere Liste head = null
	private element head;
	
	//Anzahl aller erzeugten elemente
	private int n;
	
	//Konstruktor
	public AnnotatedSet()
	{
		head = null;
		n = 0;
	}
	
	//Repraesentiert ein Element, wird fuer jedes Element der Liste erzeugt
	//In: newtyp(Racer oder Fuse)
	//Out: s.unten
	protected class element
	{
		//Represent the value of element
		protected Typ valueelem; 
		
		protected element nextelem;
		protected element preelem;
		
		//Anmerkung als SortedSet
		protected SortedSet<Typ2> anmerkung; 
		
		//Erzeugt das Element
		//IN: Fuse or Racer
		element (Typ elem) 
		{ 
			this.valueelem = elem; 
			this.anmerkung = new SortedSet<Typ2>();
		}
		
		/*
		 * In: Typ
		 * Out: true wenn that schneller, sonst false
		 */
		public boolean faster(Typ that) 
		{
			return this.valueelem.faster(that);
		}
	
		//---Getter---
		// Out: Typ (rep. nextelem)
		public element getnext()
		{
			return nextelem;
		}
		// Out: Typ (rep. preelem)
		public element getpre()
		{
			return preelem;
		} 
		// Out: Fuse or Racer (rep. value)
		public Typ getvalue()
		{
			return valueelem;
			
		}	
		/*
		 * Out: Gibt die liste mit anmerkungen zurueck
		 */
		public SortedSet<Typ2> getList()
		{
			return anmerkung;
		}
		//---Setter:
		// IN: Typ (rep. nextelem)
		public void setnext(element a)
		{
			this.nextelem = a;
		}
		// IN: Typ (rep. preelem)
		public void setpre(element a)
		{
			this.preelem = a;
		} 
		// IN: Fuse or Racer (rep. value)
		public void setvalue(Typ a)
		{
			this.valueelem = a;
		}		
	}
	
	//Einfuegen eines neuen Elements am best. Pos der Liste
	//IN: WErt(Fuse,Racer) von neuem element
	public void insert(Typ newelem) 
	{
		//Falls Liste leer head = neues Element
		if (head == null) 
		{
			// Erzeuge neues Element
			element neu  =  new element(newelem);
			// Setze head = neues Element
			head = neu;
			// das naechste bzw preelement von neu auf neu zeigen lassen
			neu.nextelem = neu;
			neu.preelem = neu;
		}
		//Sonst einfuegen des Elements bestimmte Pos
		else 
		{
			//neues element
			element neu = new element(newelem);
		
			//ereugen des iterator fuer aktiv liste
			iterator b = new iterator();
			
			//Pointer auf Head
			element temppointer = head;
			
			//Wenn nur ein Element vorhanden
			if(!b.hasNext())
			{
				//Verlinkungen setzen
				neu.nextelem = temppointer;
				neu.preelem = temppointer;
				temppointer.preelem = neu;
				neu.preelem.nextelem = neu;
				
				//Ueberpruefen welches der zwei elemente hoeher ist,setzen des head dementsprechend 
				if(!neu.faster(head.valueelem))
				{
					head = neu;
				}
			}
			else
			{	
				//Durchgehen der Liste
				for(int i = 1;i<=n;i++)
				{
					assert n >= 0 : 0;
					assert i >= 0 : 0;
					//Ist element nicht groesse dann 
					if(!neu.faster(temppointer.valueelem))
					{
						neu.nextelem = temppointer;
						neu.preelem = temppointer.preelem;
						neu.nextelem.preelem = neu;
						neu.preelem.nextelem = neu;
						if(temppointer == head)
							head = neu;
						//Wenn pos gefunden break
						break;
					}
					//insert in last pos
					if(temppointer.nextelem == head)
					{
						neu.nextelem = head;
						neu.preelem = head.preelem;
						neu.nextelem.preelem = neu;
						neu.preelem.nextelem = neu;
						break;
					}
					
					//Pointer eine Pos weiter
					temppointer = temppointer.nextelem;
				}
			}
		}
		//Anzahl der Elemente um eins Erhoehen
		n = n+1; 
	}
	
	//Rep. Pointer auf elemente der Liste
	protected class iterator implements iteratorInterface2<Typ,Typ2>
	{
		//Pointer auf erstes element in der Liste setzen
		protected element pointer;
		
		/*
		 * Constructor
		 */
		iterator()
		{
			this.pointer = head;
		}
		
		//Gibt das naechste Element zurueck und verschiebt Pointer auf dieses
		//IN: void
		//Out: Typ
		public Typ next() 
		{
				//A elem = p.elem; p = p.next; return elem;
				pointer = pointer.nextelem;
				return pointer.valueelem;		
		}
		//Gibt aktuelle Pos zuerueck
		//Out: Typ
		public Typ getpointer()
		{
			return pointer.getvalue();
		}
		//Gibt zurueck ob ein naechstes Element exestiert
		//Out: boolean
		public boolean hasNext() 
		{	
			//pointer auf naechstes element
			//liste leer
			if(head == null)
				return false;
			
			//Wenn pointer auf head -> ende der Liste erreicht -> kein nachfolger
			if(pointer.nextelem == head)
				return false;
			
			return true;
		}
		//Iterator Anmerkungen
		public iteratorInterface<Typ2> iterator()
		{
			iteratorInterface<Typ2> it_anmerkung = pointer.getList().iterator();
			//Ueberpruefung ob Liste der Anmerkungen Leer
			if(it_anmerkung.getpointer() == null)
				return null;
			else
				return it_anmerkung;
		}
		
	}
	//public methode um auf Methode iterator zugreifen zu koennen
	//Out: class iterator();
	public iteratorInterface2<Typ,Typ2> iterator() 
	{
		return new iterator();
	}
	//Fuegt an pos anmerkung hinzu
	//IN: position(Typ), anmerkung(Typ2)
	public void annotated(Typ pos, Typ2 anmerkung) 
	{
		//erzeuge iterator
		iterator temp_it = new iterator();
		
		//
		Typ temp_elem = temp_it.getpointer();
		
		/*
		 * Main for schleife, alle elemente durchgrasen
		 * und abchecken
		 */
		for(int i = 1;i<=n;i++)
		{
			assert i >= 0 : 0;
			if(pos == temp_elem)
			{
				temp_it.pointer.getList().insert(anmerkung);
				break;
			}
			temp_elem = temp_it.next();
		}
		
	}
	
	//Gibt Annotated Liste in form eines Strings aus
	//Out: String
	public String toString()
	{
		String out = "";
		iterator temp_iterator_pos = new iterator();
		
		//ueberprueft ob liste leer
		boolean check_pos = true;
		
		//liste leer
		if(n == 0)
			check_pos = false;
		
		while(check_pos)
		{
			element pos = temp_iterator_pos.pointer;
				out = out +"\n"+ temp_iterator_pos.pointer.getvalue().getValue()+": ";//time oder speed von Fuse oder Racer
				out = out + pos.anmerkung.toString();
			check_pos = temp_iterator_pos.hasNext(); //naechstes element pruefen
			temp_iterator_pos.next();//iterator wird erhoeht
		}
		return out;
	}
	
	//gibt Durchhaltevermoegen in form eines Strings aus
	//OUT: String
	public String toString_durchh()
	{
		String out = "";
		iterator temp_iterator_pos = new iterator();
		
		//ueberprueft ob liste leer
		boolean check_pos = true;
		
		//Liste leer
		if(n == 0)
			check_pos = false;
		
		
		while(check_pos)
		{
			element pos  = temp_iterator_pos.pointer;
				out = out +"\n"+ temp_iterator_pos.pointer.getvalue().getdurchh()+": "; //durchhaltevermoegen des elements an der aktuellen position
				out = out + pos.anmerkung.toString_durchh(); //durchhaltevermoegen des elements in der anmerkung des elements an der aktuellen position
			check_pos = temp_iterator_pos.hasNext();
			temp_iterator_pos.next(); //iterator wird erhoeht
		}
		return out;
	}
	
}

